#include <iostream>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <algorithm>

using namespace std;

static uint64_t pi_function(const vector<uint64_t>& primes, uint64_t num) {
    ++num;
    auto it = lower_bound(primes.begin(), primes.end(), num);
    return it - primes.begin(); 
}

static bool prime(uint64_t n) {
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    if (n < 2)
        return false;
    for (uint64_t i = 3; i * i <= n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}

int main() {
    constexpr uint64_t target = static_cast<uint64_t>(1e12);
    constexpr uint64_t limit = target / 6 + 1;
    vector<uint64_t> primes;
    for (uint64_t i = 2; i <= limit; ++i) {
        if (prime(i)) 
            primes.push_back(i);
    }
    cout << primes.size() << " primes below " << limit << endl;
    return 0;
#if 1
    auto func1 = [&](){ return pi_function(primes, static_cast<uint64_t>(pow(target, 1.0 / 7))); };
    auto func2 = [&](){
        uint64_t r = 0;
        for (int i = 0; primes[i] <= static_cast<uint64_t>(pow(target, 1.0 / 3)); ++i) {
            uint64_t p1 = primes[i];
            uint64_t p2 = target / p1 / p1 / p1;
            r += pi_function(primes, p2);
            if (p1 <= p2)
                --r;
        }
        return r;
    };
    auto func3 = [&](){
        uint64_t r = 0;
        for (int i = 0; primes[i] < static_cast<uint64_t>(pow(target, 1.0 / 3)); ++i) {
            for (int j = i + 1; j < primes.size() && primes[j] < target / primes[i]; ++j) {
                uint64_t p1 = primes[i];
                uint64_t p2 = primes[j];
                uint64_t p3 = target / p1 / p2;
                // cout << p1 << ' ' << p2 << ' ' << p3 << ' ' << endl;
                if (p3 > p2) 
                    r += pi_function(primes, p3) - pi_function(primes, p2);
            }
        }
        return r;
    };
    cout << func1() << endl;
    cout << func2() << endl;
    cout << func3() << endl;
    // cout << func1() + func2() + func3() << endl;
#else 
    unordered_set<uint64_t> s;
    auto func1 = [&](){
        for (auto prime : primes) {
            uint64_t t = prime * prime * prime * prime * prime * prime * prime;
            if (t <= target)
                s.insert(t);
            else
                break;
        }
    };
    auto func2 = [&](){
        for (auto p : primes) {
            for (auto q : primes) {
                if (p == q)
                    continue;
                uint64_t t = p * q * q * q;
                if (t <= target)
                    s.insert(t);
                else 
                    break;
            }
        }
    };
    auto func3 = [&](){
        for (auto x : primes) {
            for (auto y : primes) {
                if (x * y * 2 > target)
                    break;
                if (x == y)
                    break;
                for (auto z : primes) {
                    if (x == z)
                        continue;
                    if (y == z)
                        continue;
                    uint64_t tmp = x * y * z;
                    if (tmp <= target)
                        s.insert(tmp);
                    else    
                        break;
                }
            }
        }
    };
    func1();
    cout << s.size() << endl;
    func2();
    cout << s.size() << endl;
    func3();
    cout << s.size() << endl;
#endif
}